DFS II

Posted on | Edited on | | Views:

专注 dfs 20 年, 粗略的说一说基于 subset 的 🌰.

Article Language: Chinese
Example Language: Java
Reading Time: 17min

Partition an Array into K Equal Sum Subsets

input: An array, and int number k.
output: Boolean whether the array can be divided into k subsets with equal sum.

  • 是否能被等分? 如果 k 能够被数组的总和整除, 则有可能存在这样 k 个子集.
  • 找到 k 个总和等于 sum/k 的子集.
  • 可以使用子集求和的方法, 或者找到所有满足条件的子集的路径.
  • 每个元素只能用一次, 所以需要一个额外的数据结构来记录是否使用过.
    It could be nicer if srot the array in descending order

It runs k times looking for a qualified subset, so the worst case would be the most O(k _ n! _ n), where n! is for seaching

String Split

input: String /char array/etc.
output: List<List> /List/ etc.

给一个 string(直接用 substring)或者 char array( 可以用 StringBuilder), 把它进行切分, 每一个被切分过的 string 长度不能超过 2.

举个 🌰, “abcd”, 返回的结果是, [[a, b, c, d], [a, b, cd], [a, bc, d], [ab, c, d], [ab, cd]].
PS: 每一个 subset 都是有双引号的, 略…

  • 每一个元素只和它后一个元素有关系.
  • 每一个分支的状态是它自己或者它和后面一个元素.
  • 后面一个元素被选过了之后失去进入下一轮的资格.

The number of element in the input is n. Every element can have at most two branches at each level. Therefore, the time complexity is O(2^n);
The height of the tree would be n as well; thus the space would be the call stack which is O(n);

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class SplitString{
    public List<List<String>> splitString(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null) {
            return new ArrayList<>();
        }
        if (s.length() == 0) {
            result.add(new ArrayList<>());
            return result;
        }

        dfs(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void dfs(String input,
            int index, List<String>sub,
            List<List<String>> result) {

        if (index == input.length()) {
            result.add(new ArrayList<>(sub));
            return;
        }

        sub.add(input.substring(index, index + 1));
        dfs(input, index + 1, sub, result);
        sub.remove(sub.size() - 1);
        if (index + 1 < input.length()) {
            sub.add(input.substring(index, index + 2));
            dfs(input, index + 2, sub, result);
            sub.remove(sub.size() - 1);
        }

    }
}

当然这道题应该有更优化的写法, 这里只考虑 dfs.

Valid Permutation of Parentheses

input: An int n represents the pair of parentheses.
output: A list of string with all valid permutation of given number pair of parentheses.

  • 在每一个位置上, 只有 2 个选择, 左括号还是右括号.
  • 放置左右括号的前提条件是什么?
  • 如果当前已经有了 n 个左括号, 那么就不能再添加左括号.
  • 如果当前左括号小于等于右括号的数量, 那么就不能再添加右括号了.

举个 🌰, input = 3, output = ["((()))", "(()())", "(())()", "()(())", "()()()"]
At every position, it has two choices, adding left or right parenthese. It has 2 * n positions. Therefore, time compexity is O(2^2n).
The recursive call would have at most 2n frames. Therefore, the space complexity is O(2n).

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class ValidParentheses{
    public List<String> validPren (int n) {
        if (n <= 0) return new ArrayList<>();

        List<String> result = new ArrayList<>();
        dfs(n, 0, 0, new StringBuilder(), result);
        return result;
    }

    private void dfs(int left, int right, StringBuilder bd, List<String> result) {
        //monitor the number of right parentheses,
        //then compare the number of left and right
        if (right >= size) {
            result.add(new String(bd));
            return;
        }

        if (left < right) {
            bd.append("(");
            dfs(left + 1, right, bd, result);
            bd.deleteCharAt(bd.length() - 1);
        }

        if (right < left) {
            bd.append(")");
            dfs(left, right + 1, bd, result);
            bd.deleteCharAt(bd.length() - 1;
        }
    }
}

K Sum II

input: An int array with UNIQUE numbers, k elements that can sum up the target, and a target number.
output: List of lists of k intergers that sum up the target.

  • 暴力求解, 基本不考虑优化.
  • 给定数组中的元素是没有重复的, 所以连 set 也不需要了, 只要保证每次只看 index 后面的元素就可以了.
  • 限定条件, 每一个结果里面只能有 k 个元素.

举个 🌰, [1, 2, 3, 4], k = 2, target = 5. 返回值为, [[1, 4][2, 3]], 也就是说, 从每一个 index 出发, 希望它每一次只和它后面的另外一个数字相加, 如果结果与 target 相等, 并且结果里面只有 2 个元素, 那么就返回这个结果.

At each level, i represents the number of i-permutations of n, where i is restricted by k. Therefore, at the each level, it’s looking for C(n, 1), C(n, 2), …, C(n, k). To add them up, 1 + C(n, 1) + … + C(n, k) = (1 + 1)^k = 2^k. If k is equal to the length of input. Then the time complexity is O(2^n).
Since we only consider answer with number of k elements, the frame of the call stack would be k, tops. So it’s O(k).
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class KSum {
    public List<List<Integer>> kSum(int[] A, int k, int targer) {
        if (A == null || A.length == 0) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        dfs(A, 0, targer, k, new ArrayList<Integer>(), result);
        return result;
    }

    private void dfs(int[] input, int index, int target, int k,
                    List<Integer> sub, List<List<Integer>> result) {
        //可以在这里返回, 也可以在 for 循环里面控制,具体参见 DFS I
        // if (target < 0 || k < 0) {
        //     return;
        // }

        //为了避免元素等于 target 的情况, subSolution 里面只有1个元素
        if (target == 0 && k == 0) {
            result.add(new ArrayList<>(sub));
            return;
        }

        for (int i = index; i < input.length && k > 0; i++) {
            if (target - input[i] >= 0) {
                sub.add(input[i]);
                dfs(input, i + 1, target - input[i], k - 1, sub, result);
                sub.remove(sub.size() - 1);
            }
        }
    }
}

Combination Sum II

input: An unordered int array with DUPLICATED elements, and a target number.
output: All UNIQUE combinations in the array which are candidate numbers sum to the target.

  • 依然暴力求解, 即使考虑优化也要考虑重复元素的问题.
  • 首先, 返回结果必须是 unique 的. 其次, 每一个元素都只能使用一次.
  • 那么就要解决重复元素能不能被重复选择的问题[笑].
  • 和 subsets II 的解法一样. 先排个序, 反正 dfs 的时间复杂度已经是指数级的了, 排个序无伤大雅.
  • 排序首先确保了结果的有序性, 有助于辨别是否重复, 其次可以选择 HashSet 或者 index 两种方法去重.

At each subsolution position i, it runs n - i times looking for candidate. There are n possible positions, where n is the length of input. Therefore, the time complexity is O(n!).
Space complexity is O(n) for call stack and using index to deduplicate (without HashSet in each level).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public CombSum {
    public List<List<Integer>> combinationSum2(int[] num, int target) {
    if (num == null || num.length == 0) {
        return new ArrayList<>();
    }
    Arrays.sort(num);
    List<List<Integer>> result = new ArrayList<>();
    dfs(num, 0, target, new ArrayList<>(), result);
    return result;
}

    private void dfs(int[] input,
                int index,
                int target,
                List<Integer> sub,
                List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(sub));
            return;
        }
        //Set<Integer> occ = new HashSet<>();
        for (int i = index; i < input.length; i++) {
            //if (target - input[i] >= 0 && occ.add(input[i])){
            if (target - input[i] >= 0 && (i == index ||
                input[i - 1] != input[i])) {

                sub.add(input[i]);
                dfs(input, i + 1, target - input[i], sub, result);
                sub.remove(sub.size() - 1);
            }
        }
    }
}

Combination of Coins

input: A target value and a list of the value of each coins.
output: A List of lists of candidates of number of each coins that can add up to the target.

  • 每一层的状态取决于当前层的 target 大小. 所以需要一个动态的变量来判断分支数量.
  • 我们希望把层数控制在 coin 的数量而不是 target 的大小, 因为如果 coin 的面值包含 1 的话, 那么层数就是 target 的大小, 如果 target 很大, 就会爆栈.

At each node of the recursion tree, it has current target / valueOfCoin states. Overall, the one has the most branches is the coin that has smallest value. The states of the node is whatever the factor is. Suppose that factor is k and the number of coin is n. The time complexity is k^n.
Space is the number of coins.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class CombCoin{
    public List<List<Integer>> findCoins(int n, int[] coins) {
        if (n <= 0) {
            throw new IllegalArgumentException("Invalid input");
        }
        if (coins == null || coins.length == 0) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        dfs(n, 0, coins, new ArrayList<>(), result);
        return result;
    }

    private void dfs(int moneyLeft, int level, int[] coins, List<Integer> sub, List<List<Integer>> result) {
        if (level == coins.length) {
            if (moneyLeft == 0) result.add(new ArrayList<>(sub);
            return;
        }
        int factor = moneyLeft / coins[level];
        for (int i = 0; i <= factor; i++) {         //add 0 ~ factor number of coins
            sub.add(i);
            dfs(moneyLeft - coins[level] * i, level + 1, coins, sub, result);
            sub.remove(sub.size() - 1);
        }
    }
}

Cartesian Product

input: A 2D array with different length of column in each row.
output: List of lists of Catesian product such that A×BxC = {(x,y,z)|x∈A ∧ y∈B ∧ z∈C};

  • 从每一行的第 0 列开始遍历, 直到最后一行, index == input.length;
  • 每一个行的元素长度有可能不一致, 考虑越界问题.
  • 这里面 for loop 不再是控制层数而是控制每一层的分支, 所以需要退出条件.
  • 举个 🌰, 给定一个二维数组[[1, 2, 3],[4, 5],[6, 7, 8]], 它的层数和 row 相关, 分支最多不超过 column 的最大值.


Suppose the matrix has n rows and m columns. It has at most n levels, and at each level, a node has at most m branches. Thus time complexity is O(m^n);
No extra space is used besides the call stack, which is the number of row, O(n).

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class CarteProduct {
   public List<List<Integer>> getSet(int[][] input) {
        if (setList == null || setList.length == 0) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        dfs(input, 0, new ArrayList<>(), result);
        return result;
    }

    private void dfs(int[][] input,
            int row, List<Integer> sub,
            List<List<Integer>> result) {

        if (row == input.length) {
            result.add(new ArrayList<>(sub));
            return;
        }

        for (int i = 0; i < input[row].length; i++) {
            sub.add(input[row][i]);
            dfs(input, row + 1, sub, result);
            sub.remove(sub.size() - 1);
        }
    }
}

All Factors Of A Number

input: An int.
output: A list of list of all candidates that the production is given number.

  • 从 2 开始找到 input 的完全平方根的整数为止.
  • 需要注意的是, 什么时候继续向下除, 什么时候停止.
  • 和前面找 sum 的题差不多, 只是需要注意一下乘除法的细节.


For each number at a level, it has sqrt(n) choices to run (although situations are optimized in the code). The recursive call has the most sqrt(n) times. The time complexity is O(sqrt(n) ^ sqrt(n)). LOGN^FACTOR
Sapces is the call stack which is sqrt of n.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class AllFactors{
    public List<List<Integer>> factors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(2, n, new ArrayList<>(), result);
        return result;
    }
    private void dfs(int startPoint,
            int quotient,
            ArrayList<Integer> sub,
            List<List<Integer>> result) {

        if (quotient <= 1) {
            result.add(new ArrayList<>(sub));
            return;
        }

        for (int i = startPoint; i <= quotient; i++) {          //corner case: n = 2
            int curFactor = i * i <= quotient ? i : quotient;   //划重点
            if (quotient % curFactor == 0) {
                sub.add(curFactor);
                dfs(curFactor, quotient / curFactor, sub, result);
                sub.remove(sub.size() - 1);
            }
            if(i * i > quotient) break;
        }
    }
}

感谢@景阳同学的友情支持~笔芯 ❤